1. Field of the Invention
The present invention relates to combination multiplication and addition operations in a computing environment. More particularly, the present invention relates to an apparatus for performing nonparallel and parallel multiplication/addition operations, and a method for operating that apparatus.
2. The Background Art
In modern computers, there exists a mathematical function N=A*B+C which is performed frequently. Although the entire function is important, the prior art performs the multiplication first, and then adds xe2x80x9cCxe2x80x9d to the result.
Two types of methods are used commonly in computers to perform the multiplication/addition calculation, parallel and traditional.
Traditional multiplication divides the two numbers into upper and lower halves. The upper and lower halves are then multiplied together in succession, and the results of those multiplications are then added together, forming the final result of the multiplication.
Therefore, two 32-bit numbers xe2x80x9cAxe2x80x9d and xe2x80x9cBxe2x80x9d being multiplied together will each be broken into halves, making xe2x80x9cAhxe2x80x9d and xe2x80x9cAlxe2x80x9d represent the upper and lower halves of the number xe2x80x9cAxe2x80x9d, and xe2x80x9cBhxe2x80x9d and xe2x80x9cBlxe2x80x9d represent the upper and lower halves of the number xe2x80x9cBxe2x80x9d. The functions Ah*Bh+Ch=Nh, and Al*Bl+Cl=Nl are then performed, and the two results Nh and Nl are then put back together as [Nh] [Nl] to form the final result N. This method of combining three numbers requires 2 identical apparatus""s, each operating in parallel on different halves of the calculation.
Parallel multiplication, the second method, takes the same numbers xe2x80x9cAxe2x80x9d, xe2x80x9cBxe2x80x9d and xe2x80x9cCxe2x80x9d and also breaks each of them into upper and lower halves. The lower half of each is sign extended to the size of the original number. The lower halves are then multiplied together on one apparatus having the capability to operate on numbers having that width, and the upper halves are combined using an apparatus having the capability to operate on the smaller width. For example, when 32-bit binary numbers are being combined, the upper and lower halves are each 16-bits. The lower halves are sign extended to 32 bits, and multiplied and added together using 32-bit hardware at the same time that the upper halves are being combined using 16-bit hardware. The upper and lower halves are then recombined in an adder.
While suitable for their intended purposes, the traditional and parallel combinatory apparatus""s are different, and therefore require more space to implement than would otherwise be required, if traditional and parallel operations were able to be performed using the same apparatus.
It would therefore be beneficial to provide an apparatus which can be used to perform both traditional and parallel mathematical operations.
An apparatus for multiplying a first number and a second number together is described, each of the numbers having a width of 8, 16, 32, 64 or 128-bits or more. The 32-bit embodiment of the apparatus comprises a booth recoder having two inputs and 16 outputs, the recoder determining 16 individual booth groups associated with the second number and providing one partial product per booth group on individual ones of the 16 outputs. The apparatus further comprises first, second, third and fourth 4:2 compressors each having four inputs individually coupled to consecutive ones of the booth recoder outputs, a carry output and a sum output, fifth and sixth 4:2 compressors each having four inputs, the first and third inputs of the fifth and sixth compressors being individually coupled to the sum outputs of the first, second, third and fourth compressors respectively, the second and fourth inputs of the fifth and sixth compressors being individually coupled to the carry outputs of the first, second, third and fourth compressors respectively. The apparatus further includes a seventh 4:2 compressor having four inputs, the first and third inputs of the seventh compressor being individually coupled to the sum outputs of the fifth and sixth compressors respectively, the second and fourth inputs of the seventh compressor being individually coupled to the carry outputs of the fifth and sixth compressors respectively and an adder having two inputs individually coupled to the carry and sum outputs of the seventh compressor, and an output.